package com.sgffsg.learn.javalib.algorithm.sort;

import java.util.Arrays;

/**
 * @author: lmk
 * @date: 2024/4/23
 * @desc:
 */
public class QuickSortTest {

    public static void main(String[] args) {
        //int[] nums = new int[]{-1, 3, 4, 6, 9, 2, -7};
        int[] nums = new int[]{9, 6, 4, 2, 3, 5, 7, 0, 1};
        QuickSortTest quickSortTest = new QuickSortTest();
        System.out.println("pre res = " + Arrays.toString(nums));
        quickSortTest.quickSort(nums, 0, nums.length - 1);
        System.out.println("end res = " + Arrays.toString(nums));

    }

    private void quickSort(int[] nums, int leftIndex, int rightIndex) {
        System.out.println("quickSort  left = " + leftIndex + ",right = " + rightIndex + ",nums = " + Arrays.toString(nums));
        if (leftIndex >= rightIndex) {
            return;
        }
        int left = leftIndex;
        int right = rightIndex;
        int anchor = left;
        while (left < right) {
            while (left < right && nums[right] >= nums[anchor]) {
                right--;
            }
            while (left < right && nums[left] <= nums[anchor]) {
                left++;
            }

            System.out.println("find  left = " + left + ",right = " + right + ",nums = " + Arrays.toString(nums));
            swap(nums, left, right);
        }
//        if (anchor != left) {
        swap(nums, anchor, left);
        quickSort(nums, leftIndex, left - 1);
        quickSort(nums, left + 1, rightIndex);
//        }
    }

    private void swap(int[] nums, int left, int right) {
        System.out.println("swap  left = " + left + ",right = " + right);
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }

}
